package logic

import "fmt"

//Trie树常用的应用场景
//（1） 字符串检索
//事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
//举例：
//给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
//给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
//
//（2）字符串最长公共前缀
//Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。
//举例：
//给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？
//解决方案：首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线（Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。
//而最近公共祖先问题同样是一个经典问题，可以用下面几种方法：
//1. 利用并查集（Disjoint Set），可以采用采用经典的Tarjan 算法；
//2. 求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum Query，简称RMQ）问题了；
//
//（3）排序
//
//Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
//比如给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。
//
//（4） 作为其他数据结构和算法的辅助结构
//如后缀树，AC自动机等
//
//（5）词频统计
//trie树在这里的应用类似哈夫曼树，
//比如词频统计使用哈希表或者堆都可以，但是如果内存有限，就可以用trie树来压缩空间，因为trie树的公共前缀都是用一个节点保存的。
//
//（6）字符串搜索的前缀匹配
//trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
//Trie树检索的时间复杂度可以做到n，n是要检索单词的长度，
//如果使用暴力检索，需要指数级O(N2)的时间复杂度。

//Trie根节点
type Trie struct {
	root *Node //根节点,root字段中的node包含所有属于该根结点数据
	size int   //当前Trie树节点的个数
}

//Node节点
type Node struct {
	char   rune           //字符
	childs map[rune]*Node //所有的子节点用map来存
	Data   interface{}    //自定义数据
	deep   int            //深度
	isTerm bool           //是否是一个字符串的结尾(完整的字符串)
}


//构造一个Trie树
func NewTrie() *Trie {
	return &Trie{
		root: NewNode(' ', 1),
		size: 1,
	}
}

//生成一个节点,传入字符,深度
func NewNode(char rune, deep int) *Node {
	return &Node{
		char:   char,                     //字符
		childs: make(map[rune]*Node, 16), //保存子节点的map
		deep:   deep,                     //深度
	}
}

//字符串加入Trie树流程: eg abc加入Trie树中,先将abc打散成3个字符,每个都遍历一下
//先遍历a,看看a是否包含在根结点中的childs中,如果存在,则继续往下找b,看b是否存在...
//一直到结尾。如果a不存在,则新建一个分支
func (t *Trie) Add(key string, data interface{}) {

	var parent *Node = t.root //1:将根结点的node赋值给parent(父节点,第一次时候,父节点就是根节点)
	//将根结点指针地址赋给parent,那么对parent的修改就是对根结点的修改
	allChars := []rune(key) //2:将字符串转成字符,遍历它

	for _, char := range allChars {
		node, ok := parent.childs[char] //查看当前字符是否在根结点的childs中
		if !ok {
			//如果不在,则新创建这个字符的node,深度=父节点的deep+1

			node = NewNode(char, parent.deep+1)
			parent.childs[char] = node //修改根结点,将这个新建的node加入根结点的childs中
		}
		//如果在,则继续往下找,将查找到的这个node,赋值给parent变量,作为下一次遍历的根结点
		//下一次直接从parent这个变量中继续查找,一直到循环结束
		parent = node
	}

	//将所有字符遍历完成之后,这个字符串就已经加入Trie树了
	//这时,parent这个变量为最后一个字符的node,那么将数据加入进这个node的Data字段中
	parent.Data = data
	parent.isTerm = true //是一个字符串的结束
}

//从Trie中查找,前缀搜索
func (t *Trie) PrefixSearch(key string, limit int) (nodes []*Node) {

	var node = t.root       //将根结点的node赋值给node变量,来判断是不是在根节点下面
	allChars := []rune(key) //将传进来的字符串转为rune(字符)类型的切片
	//fmt.Println(allChars)
	for _, char := range allChars { //遍历这个字符切片

		//看看当前这个字符是否在根结点的childs中存在
		child, ok := node.childs[char]
		if !ok {
			//如果不存在,查找结束,则返回空
			return
		}
		//如果存在,则将当前查找到的这个节点,赋值给node,继续往下查找
		node = child
	}

	fmt.Printf("prefix node:%+v\n长度为:%d\n", node, len(node.childs))

	//这时候已经遍历完字符切片了,就找到了最后一个节点,
	//这时候将这最后一个节点下面的所有子节点返回就可以了!
	//这样比如以ab开头的所有子节点都找到了!
	//将ab开头的所有子节点都使用广度优先搜索算法加入队列

	//下面是将上面找到的节点,看看是否是叶子节点,是叶子节点,加入队列,继续循环，
	//不是叶子节点,则查找他的childs，如此往复，直到最后！！！

	var queue []*Node //队列
	//将刚才最后一个查找到的节点加入队列中,队列中的一个元素就是一个节点
	queue = append(queue, node)

	//fmt.Printf("queue队列的长度为:%d\n", len(queue))

	//如果queue的个数>0,则
	for len(queue) > 0 {

		var q2 []*Node
		//(1)遍历这个队列:广度优先算法
		for _, n := range queue {
			if n.isTerm == true {
				//如果这个节点已经是最后一个节点(已经是一个字符串了)
				//将这个节点加入到nodes(返回切片中)
				//如果nodes中node的个数大于限制的个数,则直接返回查找结果
				//如果不大于,则继续查找
				fmt.Printf("n is leaf node:%v", n)

				if len(nodes) >= limit {
					return
				} else {
					nodes = append(nodes, n)
				}
				//continue
			}
			//将其下面的所有叶子节点加入到队列中
			//之后继续遍历queue,这时候queue中不是一个node了,还包含刚才查找到的node
			for _, v := range n.childs {
				q2 = append(q2, v) //当前节点的q2中存的是这个节点的childs,都不是完整的字符串
			}
		}
		//将刚才所有找到的节点加入queue中,这时候看for循环的判断,queue的长度是>0的,所以继续往下查找:广度优先算法
		//什么时候退出循环呢？就是当nodes的长度大于limit时候,就退出这个循环,返回nodes(查找结果)
		queue = q2 //如果queue的长度=0,则遍历结束,如果不是0,则继续遍历这个queue(中存放的全是叶子节点)
	}

	return
}

//敏感词过滤(字符串检索),查看是否是由敏感词组成的Trie树中的一个单词
func (t *Trie) Search(key string) bool {
	var node = t.root //将根结点的node赋值给node变量,来判断是不是在根节点下面
	allChars := []rune(key)

	for _, char := range allChars { //遍历这个字符切片

		//看看当前这个字符是否在根结点的childs中存在
		child, ok := node.childs[char]
		if !ok {
			//如果不存在,查找结束,则返回false
			return false
		}
		//如果存在,则将当前查找到的这个节点,赋值给node,继续往下查找
		node = child
	}

	fmt.Printf("prefix node:%+v\n长度为:%d\n", node, len(node.childs))
	//测试就遍历完字符串,找到该字符串最后一个node的isTerm是否是true，true则是敏感词,否则不是
	if node.isTerm == true {
		//是敏感词
		return true
	} else {
		return false
	}
}
